AEL CS Encyclopedia™ – Reverse Engineering (Week 3 Algorithms)

Source Markdown File: Week_3_Practical_Reverse_Eng_EN.md Open Raw Markdown

🏛️ Algorithms Forensics & Architectural Inspection

In this specialized Practical Reverse Engineering wing, we transcend the high-level theoretical definitions of algorithms. Here, we delve into the rigorous architectural mechanics of Big O Complexity by disassembling compiled machine code and analyzing exact Call Stack behavior during searching and sorting operations.

===================================================================================
                       THE ALGORITHMS INSPECTION ENGINE
===================================================================================

  [ Unsorted / Unindexed Memory Structures ]
             │
             ├─► Linear Search  ──> O(n)     ──> Sequential Memory Traversal
             ├─► Binary Search  ──> O(log n) ──> Divide & Conquer Pointer Arithmetic
             ├─► Selection Sort ──> O(n²)    ──> Quadratic Register Swaps
             └─► Merge Sort     ──> O(n log n) ──> Recursive Stack Allocation

===================================================================================

🔬 The Analytical Disassembly Suite

1. Linear vs Binary Search Architectural Traversal

Examining the generated x86_64 Assembly execution paths reveals the stark operational contrast between sequential looping and logarithmic pointer manipulation:

# Linear Search (Loop Traversal)
.L2:
    cmpl  %esi, (%rdi,%rax,4)  # Compare current element with target
    je    .L5                  # Jump if equal (found)
    incq  %rax                 # Increment index
    cmpq  %rdx, %rax           # Check loop bound
    jne   .L2                  # Repeat loop

# Binary Search (Pointer Halving)
.L10:
    leaq  (%rsi,%rdx), %rax    # (low + high)
    shrq  $1, %rax             # Divide by 2 (Bitwise Shift Right)
    cmpl  %ecx, (%rdi,%rax,4)  # Compare middle element
    ...

2. Call Stack Disassembly & Recursive Allocation

Merge Sort fundamentally relies on recursive call execution. Inspecting the machine code via objdump demonstrates exactly how runtime stack frames are allocated dynamically to support the divide-and-conquer paradigm:

$ objdump -d mergesort
...
100004a10: 55                    pushq %rbp
100004a11: 48 89 e5              movq  %rsp, %rbp
100004a14: 48 83 ec 30           subq  $48, %rsp      # Allocating stack space for sub-arrays
...
100004a3b: e8 d0 ff ff ff        callq _mergesort     # Recursive call (left half)
100004a48: e8 c3 ff ff ff        callq _mergesort     # Recursive call (right half)
100004a55: e8 80 01 00 00        callq _merge         # Merge subroutine
...

subq $48, %rsp: Explicitly reserves 48 bytes within the current stack frame to maintain sub-array pointer addresses.
callq _mergesort: Invokes the recursive self-call, systematically pushing return addresses onto the physical call stack until reaching the base case.

⚙️ Physical Cache Efficiency & Memory Hierarchy

In production-grade engineering, algorithmic execution speed is dictated not solely by asymptotic instruction counts, but heavily by hardware-level memory access patterns across the CPU L1/L2 Cache subsystem.

💡 Deconstructing Hardware Prefetching

The Cache Miss Bottleneck: Algorithms exhibiting non-contiguous, random memory leaps trigger expensive CPU cache misses, forcing processor pipeline stalls while fetching cache lines from slow main memory (RAM). Conversely, linear contiguous array traversals fully benefit from hardware prefetching mechanisms.